The present invention relates generally to relational database systems, and more specifically, to maintenance of an index B-Tree during repetitive sequential database inserts.
An index B-Tree (e.g., binary tree index) is a data structure that can be used by a Database Management System (DBMS) and/or Relational Database Management System (RDBMS) to organize index data (e.g., data table key fields, index key values, etc.) in a logical tree, maintained in a sorted arrangement, to enable efficient index data searching.
As data records are inserted into database table(s), corresponding index entries are added to an index B-Tree in an appropriate position in an index leaf page (e.g., an allocated space representing a group of index entries and/or B-Tree leaves) based on an index value magnitude positioned between other respective lower or higher index value B-Tree leafs (e.g., index entries). Each index leaf page has a fixed size in a DBMS and when an insert operation exceeds the capacity of an index leaf page (e.g., B-Tree leaf consumption) an “index split” operation is performed. An “index split” allocates and creates a new index leaf page and moves part of the information from an original index leaf page into the new index leaf page. The index split results in two index leaf pages comprising empty B-Tree leaves capable of storing additional data (e.g., index key values).
The process of performing an index B-Tree split and the effect on modifying a B-Tree structure can be considered an expensive DBMS operation due to the overhead of copying and arranging data in an index B-Tree during the index split. As page space is allocated during an index split, computing resources such as, but not limited to, CPU and I/O can cause index locking and during numerous linear sequential insert operations, index leaf pages can become quickly filled. When available B-Tree pages are exhausted, an index split can be performed and as each new B-Tree page is created and filled, a linear sequential insert operation can be slowed due to pauses caused by each index split (e.g., synchronous operation).